package search;

import java.util.Arrays;

/**
 * 斐波那契搜索
 */
public class FibonacciSearch {

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        /*int index = FibonacciSearch(arr, 1234);
        System.out.println(index);*/
        int index = FibonacciSearch2(arr, 0, arr.length - 1, 5);
        System.out.println(index);
    }

    /**
     * 获取斐波那契数列
     *
     * @param size
     * @return
     */
    public static int[] getFibonacci(int size) {
        int[] arr = new int[size];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < size; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr;
    }


    /**
     * 斐波那契搜索 不使用递归
     *
     * @param arr
     * @param value
     * @return
     */
    public static int FibonacciSearch(int[] arr, int value) {
        //获得斐波那契数列的首尾
        int low = 0;
        int high = arr.length - 1;
        //获得斐波那契数列
        int[] fibonacci = getFibonacci(high + 1);
        //看看数组的长度匹配斐波那契数列的哪个值
        int k = 0;
        while (high > fibonacci[k] - 1) {
            k++;
        }
        //创建数组 用于存放数组
        //因为可能新数组长度比原数组大 所以需要拷贝
        int[] temp = Arrays.copyOf(arr, fibonacci[k]);
        //如果新数组长 拷贝后超过长度的地方默认为0
        //为了保持有序 将超过的部分都置为最大值
        for (int i = high + 1; i < fibonacci[k]; i++) {
            temp[i] = arr[high];
        }

        //开始寻找
        while (low <= high) {
            int mid = low + fibonacci[k - 1] - 1;
            if (value < temp[mid]) {
                //说明在左边
                high = mid - 1;
                k--;
            } else if (value > temp[mid]) {
                //说明在右边
                low = mid + 1;
                k -= 2;
            } else {
                //说明找到了
                //但是找到了有两种情况
                if (mid <= high) {
                    //情况一：找到的数据下标位置小于high 说明没超过原数组范围就找到了
                    return mid;
                } else {
                    //情况二：找到的数据下标位置大于high 说明超过原数组范围找到了
                    return high;
                }
            }
        }
        return -1;
    }

    /**
     * 斐波那契搜索递归
     *
     * @param arr
     * @param left
     * @param right
     * @param value
     * @return
     */
    public static int FibonacciSearch2(int[] arr, int left, int right, int value) {
        if (left > right) {
            return -1;
        }
        //获取斐波那契数列
        //注意 如果数组太短 斐波那契数列就只有两个数 完全不够 所以需要+1
        int[] fibonacci = null;
        if (right - left < 4) {
            fibonacci = getFibonacci(5);
        } else {
            fibonacci = getFibonacci(right + 1);
        }

        //看看数组的长度匹配斐波那契数列的哪个值
        int k = 0;
        while (right > fibonacci[k] - 1) {
            k++;
        }
        //创建数组 用于存放数组
        //因为可能新数组长度比原数组大 所以需要拷贝
        int[] temp = Arrays.copyOf(arr, fibonacci[k]);
        //如果新数组长 拷贝后超过长度的地方默认为0
        //为了保持有序 将超过的部分都置为最大值
        for (int i = right + 1; i < fibonacci[k]; i++) {
            temp[i] = arr[right];
        }
        int mid = left + fibonacci[k - 1] - 1;
        if (value < temp[mid]) {
            return FibonacciSearch2(arr, left, mid - 1, value);
        } else if (value > temp[mid]) {
            return FibonacciSearch2(arr, mid + 1, right, value);
        } else {
            if (mid <= right) {
                return mid;
            } else {
                return right;
            }
        }

    }
}
